package com.fr.lintcode;

import org.junit.Test;

public class Q1251 {

	/**
	 * @param nums: a list of integers
	 * @param m:    an integer
	 * @return: return a integer
	 */
	public int splitArray(int[] nums, int m) {
		// write your code here
		if (nums == null || nums.length == 0 || m > nums.length) {
			return 0;
		}
		long left = 0;
		long right = 0;
		for (int i : nums) {
			right += i ;
			if(left < i ) {
				left = i ;
			}
		}
		while (left < right) {
			long mid = (left + right) / 2;
			int rs = check(nums, mid, m);
			if(rs > 0) {
				left = mid + 1;
			}else {
				right = mid;
			}
		}
		return (int)left;
	}
	private int check(int[] nums, long mid, int m) {
		int min = 1;
		int sum = 0;
		for(int i = 0; i < nums.length; i++) {
			sum += nums[i];
			if(sum > mid) {
				sum = nums[i];
				min ++;
				if(min > m) {
					return 1;
				}
			}
		}
		return min - m;
	}

	@Test
	public void testA() {
		int [] nums = {5,1,3,5,10,7,4,9,2,8};
		int m = 1;
		System.out.println(splitArray(nums, m));
	}
}
